package day3;

import java.util.Arrays;

public class oj2 {
    //排序 遍历 O(n*2)
    public int MoreThanHalfNum_Solution1(int [] array) {
        if(array == null || array.length == 0) {
            return 0;
        }
        Arrays.sort(array);
        int len = array.length;
        int midNum = array[(len/2)];
        int count = 0 ;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == midNum) {
                count++;
            }
        }
        if(count > (len/2)) {
            return midNum;
        }else {
            return 0;
        }
    }


    //众数 O（n）
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) {
            return 0;
        }
        int result = array[0];
        int time = 1;
        for(int i = 1; i < array.length; i++) {
            if(time != 0) {
                if(result != array[i]) {
                    --time;
                } else {
                    ++time;
                }
            } else {
                result = array[i];
                time = 1;
            }
        }
        time = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == result) {
                time++;
            }
        }
        if(time > (array.length/2)) {
            return result;
        } else {
            return 0;
        }
    }
}
